n = 1000;
ty = [0,1,0,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,1,0,1,1,0,1,1,1,1,1,0,1,1,0,1,1,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,0,1,0,1,0,1,0,1,1,0,1,0,1,1,1,1,1,1,1,0,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,0,1,0,0,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,0,1,1,1,1,1,0,1,1,1,0,0,0,0,1,1,1,1,1,1,1,1,0,0,1,0,1,0,1,1,0,0,1,0,1,1,0,1,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,1,0,0,0,1,1,1,1,0,0,1,1,1,0,1,1,0,0,0,1,0,1,1,0,1,1,0,1,1,0,1,0,1,1,1,0,1,0,0,0,1,0,1,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,0,0,0,1,0,1,0,1,0,1,0,0,1,1,1,1,0,1,1,0,1,1,0,1,1,1,0,1,1,0,0,1,1,1,0,0,0,1,0,0,1,1,1,0,0,0,0,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,0,1,1,0,1,1,0,0,1,1,1,1,1,0,1,1,1,0,0,0,0,0,1,0,0,0,1,1,1,1,1,1,0,0,0,1,1,0,0,1,0,1,1,1,1,1,0,1,0,1,1,0,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,0,0,1,1,0,1,1,0,1,1,0,0,0,1,1,0,1,0,0,1,1,1,1,1,0,1,1,0,1,0,1,1,1,1,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,0,1,1,1,1,0,1,0,0,0,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,0,0,1,0,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,0,1,0,0,1,0,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,1,1,1,0,1,0,1,1,0,1,0,1,1,1,0,0,1,0,1,0,1,0,0,0,1,1,1,0,0,0,1,0,1,1,0,1,1,0,0,1,1,0,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,0,1,0,0,1,1,1,0,1,1,1,1,1,0,0,0,0,1,1,1,0,0,1,1,0,0,0,1,0,1,1,1,1,0,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,0,0,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,0,1,0,0,1,0,0,1,1,1,0,0,0,0,0,0,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,0,0,0,1,0,1,1,1,1,1,1,0,0,1,1,0,1,0,1,1,1,1,0,0,0,0,1,0,1,1,1,0,0,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,0,0,1,1,0,1,1,0,1,1,0,0,1,1,0,0,1,1,0,0,1,0,1,0,1,1,1,0,0,1,0,0,1,1,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,0,0,1,1,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,0,0];
price = [139,167,123,93,123,159,3,6,94,189,149,113,212,100,325,113,307,287,267,358,216,125,414,11,79,179,16,35,476,756,877,385,108,206,64,13,106,61,323,100,71,126,198,659,178,181,193,78,207,268,325,210,378,22,293,68,227,130,87,204,45,294,124,147,371,44,55,102,121,268,184,245,319,186,272,108,360,362,347,555,664,258,230,286,59,321,136,182,675,143,82,377,719,644,6,36,175,318,259,584,380,951,14,599,260,125,298,546,429,260,105,34,391,309,466,547,89,299,284,795,469,567,869,1,460,552,283,422,92,811,279,21,546,214,58,356,211,356,18,97,51,887,221,391,133,78,112,301,299,541,192,453,571,460,282,147,43,65,894,82,57,25,19,662,84,64,15,17,11,659,5,766,48,35,20,54,451,687,655,844,321,270,248,760,360,806,348,467,709,495,69,361,14,678,156,65,55,272,25,256,207,98,32,203,307,3,225,270,176,332,563,500,220,201,117,148,264,609,21,295,47,71,318,481,41,110,255,238,48,87,14,239,288,858,151,393,12,210,136,208,39,484,847,57,135,173,203,643,237,86,208,184,43,214,9,11,10,39,52,9,47,76,7,44,5,81,276,91,976,81,294,960,481,318,423,99,323,563,157,68,163,294,95,188,179,395,289,277,751,811,487,769,796,747,692,32,254,56,907,560,569,617,669,512,85,109,831,491,479,157,872,25,14,57,58,401,597,54,144,672,193,157,644,743,494,34,224,122,171,820,308,627,680,416,829,765,577,454,125,655,287,74,797,56,80,9,287,44,35,343,49,43,57,160,56,21,770,44,33,40,9,458,416,63,110,173,332,250,320,311,58,265,700,322,72,110,73,101,53,73,81,31,108,36,5,117,95,132,322,101,74,265,320,358,197,354,79,192,177,47,4,113,525,506,162,255,157,422,107,655,6,360,21,648,686,839,388,178,332,668,620,62,293,258,319,114,215,58,89,31,31,810,21,15,54,40,9,337,19,26,32,20,552,38,16,48,25,3,5,76,37,32,20,106,142,27,7,631,139,60,82,184,49,19,151,4,705,364,237,164,527,253,569,606,167,391,163,19,290,165,459,621,571,37,94,467,120,315,263,63,440,413,352,111,1,391,189,199,81,116,122,47,226,147,11,3,16,978,2,14,9,12,8,20,10,6,17,10,3,18,15,497,260,39,563,491,849,849,666,528,263,742,888,963,668,839,857,34,204,339,902,326,33,262,296,199,731,135,93,176,107,209,708,365,90,259,264,411,501,270,235,461,87,243,816,382,120,468,187,22,170,353,833,200,137,342,692,52,293,719,126,36,186,163,197,310,327,249,387,438,705,628,227,515,299,30,599,983,662,220,229,597,207,907,318,134,606,310,93,220,377,210,213,5,370,317,117,59,81,113,152,1,493,1,1,1,1,1,1,1,1,368,762,1,205,247,365,20,47,360,254,225,188,164,227,152,231,131,39,326,477,45,590,345,263,362,745,22,493,543,524,639,171,333,102,767,39,266,839,341,551,85,9,541,924,509,574,167,29,555,267,170,337,508,519,126,595,340,484,115,138,112,664,167,355,229,733,107,548,220,604,364,189,958,374,471,173,57,10,475,929,596,263,334,243,697,726,159,198,310,67,260,336,285,208,144,84,425,229,228,56,383,54,357,415,198,461,793,295,285,12,582,908,604,597,550,323,184,652,889,159,558,391,393,382,30,11,440,474,407,710,564,519,652,366,713,256,476,661,555,295,349,336,5,559,602,627,431,359,480,101,366,421,221,393,446,102,8,63,136,391,96,45,155,732,121,818,62,185,52,97,32,14,29,184,43,961,254,63,325,289,117,494,490,367,779,194,284,376,195,142,550,238,44,202,184,168,274,479,178,481,698,164,281,595,635,559,735,374,608,631,138,395,111,450,242,382,399,919,26,455,477,83,251,476,140,348,62,448,40,775,578,84,586,142,306,53,88,44,141,118,42,739,361,486,680,50,341,182,198,51,317,327,433,149,360,802,124,548,289,231,39,22,672,34,14,135,14,32,21,25,16,12,32,452,774,249,581,204,847,86,666,206,846,821,549,383,122,174,869,316,308,285,414,442,520,294,6,377,62,25,479,334,197,488,227,595,426,494,75,359,672,42,746,299,577,696,774,22,606,847,392,100,142,58,21,731,606,175,241,926,71,178,367,203,109,22,379,473,422,328,705,318,33,28,741,553,571,824,647,743,326,72,99,112,25,111,132,108,119,335,431,558,552,393,664,610,409,201,432];
time = [550,589,823,854,855,858,861,863,864,865,866,867,1654,1661,1665,1680,1688,1689,1690,1691,1692,1693,1694,1695,1696,1697,1698,1721,2608,2624,2627,2652,3070,3087,3092,3094,3102,3103,3104,3105,3106,3107,3108,3109,3110,3111,3112,3113,3114,3226,3251,3257,3260,3262,3268,3269,3270,4048,4080,4099,4122,4123,4125,4129,4131,4132,4133,4134,4135,4136,4137,4138,4139,4140,4141,4142,4143,4156,4161,4170,4178,4186,4192,4193,4194,4195,4196,4197,4198,4199,4200,4365,4378,4392,4395,4399,4400,4401,4402,4403,4404,4405,4406,4407,4408,4409,4417,4435,4437,4448,4454,4455,4456,4457,4458,4459,4460,4461,4501,4505,4510,4514,4517,4527,4533,4534,4536,4537,4538,4539,4540,4541,4542,4543,4544,4545,4559,4566,4598,4599,4600,4601,4602,4603,5527,5550,5570,5832,5842,5843,5857,5859,5861,5865,5872,5876,5887,5890,5899,5906,5916,5917,5918,5919,5920,5921,5922,5923,5924,5925,5926,5927,5928,5929,5930,5931,5958,5980,5986,5987,5988,5989,5990,5991,5992,5994,5995,5996,5997,5998,5999,6000,6001,6002,6244,6245,6264,6269,6270,6279,6280,6281,6283,6284,6285,6286,6287,6288,7142,7171,7174,7175,7176,7177,7178,7179,7180,7181,7182,7183,7184,7185,7186,7206,7220,7237,7238,7240,7241,7242,7243,7244,7245,7246,7247,7248,7249,7250,8097,8105,8115,8117,8127,8135,9059,9087,9097,9099,9100,9101,9102,9103,9147,9176,9177,9180,9183,9184,9185,9186,9187,9188,9189,9190,9191,9836,9840,9878,9879,9880,10335,10343,10356,10362,10370,10373,10377,10378,10380,10410,10414,10418,10420,10421,10422,10569,10588,10589,10597,10599,10600,10601,10602,10603,10604,10605,10606,10607,10608,10609,10610,10611,10612,10613,10631,10639,10667,10668,10669,10670,10671,10672,10673,10674,10675,11615,11639,11640,11642,11645,11646,11648,11649,11650,11651,11652,11653,11654,11655,11656,11657,11658,11659,11667,11693,11704,11705,11706,11707,11708,11709,11710,11711,11725,11742,11747,11755,11756,11758,11760,11762,11764,11765,11766,11767,11768,11769,11811,11842,11846,11847,11849,11882,12225,12269,13139,13149,13165,13169,13173,13733,13750,13754,13774,14318,14340,14348,14349,14350,14351,14352,14353,14354,14355,14356,14357,14358,14359,14360,14361,14362,14370,14392,14394,14395,14398,14401,14402,14403,14404,14405,14406,14407,14408,14409,14410,14411,14412,14413,14414,14792,14836,14852,14866,14872,14873,14874,14875,14876,14877,14878,14879,14880,15092,15130,15143,15154,15173,15182,15189,15217,15222,15223,15227,15229,15230,15231,15232,15233,15480,15486,15489,15500,15508,15513,15517,15519,15521,15524,15528,15535,15546,15550,15553,15557,15558,15561,15563,15564,15565,15566,15567,15568,15569,15570,15571,15572,16367,16380,16389,16399,16403,16404,16405,16407,16408,16409,16411,16433,16462,16468,16469,16470,16471,16472,16473,16474,16475,16476,16477,17063,17099,17104,17131,17132,17139,17142,17153,17159,17170,17172,17173,17174,17175,17872,17881,17885,17897,17900,17902,17904,17906,17908,17909,17910,17911,17912,17913,17914,17915,17916,18127,18156,18157,18158,18159,18160,18161,18162,18163,18164,18165,18166,18167,18168,18169,18170,18171,18208,18211,18223,18233,18237,18241,18242,18243,18244,18245,18246,18247,18248,18249,18250,18251,18252,18720,18740,18746,18748,18753,18755,18756,18759,18760,18761,18762,18763,18764,18875,18895,18900,18901,18904,18905,18906,18907,18908,18909,18910,18911,18912,18913,18914,18915,18916,18917,18918,18919,18955,18986,18988,18989,18990,18991,18992,18993,18994,18995,18996,18997,18998,18999,19024,19047,19049,19051,19053,19054,19055,19056,19057,19059,19060,19061,19062,19063,19064,19065,19066,19067,19068,19585,19593,19614,19618,19619,19620,19623,19624,19625,19626,19627,19628,19629,20123,20143,20144,20156,20159,20161,20164,20167,20188,20191,20217,20218,20221,20222,20223,20224,20225,20226,20227,20228,20229,20230,20231,20232,20591,20602,20608,20625,20628,20629,20631,20632,20633,20634,20635,20676,20694,20710,20712,20713,20714,20715,20716,20717,20718,20719,20720,21411,21442,21464,21467,21470,21472,21473,21474,21475,21476,21477,21478,21479,21480,21481,21482,21483,21484,21485,21486,21723,21746,21747,21759,21761,21762,21763,21764,21765,21766,21767,21769,21794,21795,21802,21810,21811,21812,21813,22107,22137,22164,22191,22232,22268,22271,22273,22274,22275,22276,22831,22843,22866,22871,22872,23544,23558,23564,23575,23576,23577,23578,23579,23580,23581,23582,23583,23584,23585,23586,23587,23588,24404,24410,24414,24417,24419,24421,24434,24439,24440,24441,24442,24443,24444,24445,24446,24447,24448,24814,24841,24845,24846,24847,24848,24849,24850,24851,24852,24853,24854,24855,24856,24857,24858,24871,24876,24877,24882,24884,24897,24904,24905,24906,24907,24908,24909,24910,24911,24912,24913,24914,24915,25537,25560,25574,25579,25580,25611,26257,26277,26282,26286,26291,26292,26293,26294,26295,26296,26297,26298,26299,26300,26301,26705,26722,27205,27218,27219,27225,27240,27256,27257,27261,27263,27264,27265,27266,27267,27268,27269,28026,28066,28068,28363,28384,28390,28392,28394,28396,28397,28398,28399,28400,28401,28402,28403,28404,28405,28406,28407,29275,29284,29290,29304,29308,29309,29312,29315,29316,29317,29318,29511,29512,29551,29554,29555,29581,29592,29612,29613,29614,29616,29618,29619,29620,29621,29622,29623,29624,29625,30171,30176,30206,30207,30208,30209,30210,30211,30212,30213,30214,30215,30231,30246,30255,30257,30258,30260,30261,30264,30265,30266,30267,30268,30269,30270,30271,30272,30273,30274,30275,30294,30322,30334,30363,30365,30371,30386,30398,30399,30400,30401,30402,30403,30404,30405,30406,30407,31265,31291,31297,31298,31300,31303,31304,31305,31306,31307,31308,31309,31815,31821,31839,31845,31857,31858,31859,32254,32271,32276,32279,32286,32288,32292,32297,33013,33021,33022,33025,33033,33041,33049,33050,33051,33052,33053,33054,33055,33056,33057,33098,33127,33131,33137,33139,33140,33141,33142,33522,33549,33574,33582,33588,33590,33592,33593,33936,33977];